@PhDThesis{Chaves:2009:MeHíBu,
author = "Chaves, Antonio Augusto",
title = "Uma meta-heur{\'{\i}}stica h{\'{\i}}brida com busca por
agrupamentos aplicada a problemas de otimiza{\c{c}}{\~a}o
combinat{\'o}ria",
school = "Instituto Nacional de Pesquisas Espaciais (INPE)",
year = "2009",
address = "S{\~a}o Jos{\'e} dos Campos",
month = "2009-03-10",
keywords = "Otimiza{\c{c}}{\~a}o combinat{\'o}ria,
meta-heur{\'{\i}}sticas, busca por agrupamentos,
localiza{\c{c}}{\~a}o de facilidades, caixeiro viajante, linha
de produ{\c{c}}{\~a}o, combinatorial optimization,
metaheuristics, clustering search, location of facilities,
traveling salesman, assembly line.",
abstract = "Esta tese apresenta um m{\'e}todo h{\'{\i}}brido, denominado
Busca por Agrupamentos (CS, do ingl{\^e}s Clustering Search), que
consiste em detectar dinamicamente regi{\~o}es promissoras no
espa{\c{c}}o de busca baseando-se na frequ{\^e}ncia em que
s{\~a}o amostradas nestas regi{\~o}es as solu{\c{c}}{\~o}es
geradas por uma meta-heur{\'{\i}}stica. Um processo de
agrupamento iterativo {\'e} executado em conjunto com a
meta-heur{\'{\i}}stica, agrupando as solu{\c{c}}{\~o}es
similares e mantendo solu{\c{c}}{\~o}es que sejam
representativas para os grupos de solu{\c{c}}{\~o}es. As
regi{\~o}es promissoras devem ser exploradas t{\~a}o logo sejam
descobertas, por meio de heur{\'{\i}}sticas de busca local
espec{\'{\i}}ficas para o problema abordado. S{\~a}o propostas
algumas aplica{\c{c}}{\~o}es do CS a diferentes problemas de
Otimiza{\c{c}}{\~a}o Combinat{\'o}ria encontrados na
literatura, tais como, Problema de \$ p\$ -Medianas Capacitado,
Problema de Agrupamento Centrado Capacitado, Problema do Caixeiro
Viajante com Coleta de Pr{\^e}mios e o Problema de Balanceamento
e Designa{\c{c}}{\~a}o de Trabalhadores em Linhas de
Produ{\c{c}}{\~a}o. Esses problemas possuem diferentes
caracter{\'{\i}}sticas e particularidades, sendo assim, {\'e}
poss{\'{\i}}vel analisar o comportamento do CS em diversas
situa{\c{c}}{\~o}es. Nessas abordagens s{\~a}o utilizadas
diferentes meta-heur{\'{\i}}sticas para gerar
solu{\c{c}}{\~o}es para o processo de agrupamento do CS, e
tamb{\'e}m um m{\'e}todo gerador de solu{\c{c}}{\~o}es
aleat{\'o}rias. Os testes computacionais mostram o potencial do
CS para resolu{\c{c}}{\~a}o desses problemas de
otimiza{\c{c}}{\~a}o, colocando-o como uma alternativa para
problemas que necessitem ser resolvidos de forma aproximada e em
um tempo computacional competitivo. Conclus{\~o}es a respeito dos
componentes e par{\^a}metros do CS tamb{\'e}m s{\~a}o
apresentadas. ABSTRACT: This thesis presents a hybrid method,
denominated Clustering Search (CS), that consists of detecting
dynamically promising regions in the search space based on the
frequence that are sampled in these regions the solutions
originated from the metaheuristic. A iterative clustering process
is executed in ensembling the metaheuristic, grouping the similar
solutions and keeping solutions that are representative to the
clusters. The promising regions must be explored as soon as they
are discovered, by means of local search heuristics. Some
applications of CS are proposed in different combinatorial
optimization problems found in literature like the Capacitated
p-Median Problem, Capacitated Centred Clustering Problem, Prize
Collecting Traveling Salesman Problem and the Assembly Line Worker
Assignment and Balancing Problem. These problems have different
characteristics and particularities, therefore, it is possible to
analyse the behavior of CS in several situations. In these
approaches different metaheuristics are utilized to generate
solutions for the clustering process of CS, and also a generator
method of random solutions. The computational tests present the
potential of CS for resolving these optimization problems, putting
it as an alternative for the problems that demand to be solved in
an approximate form and in a competitive computational time.
Conclusions regarding the components and parameters of CS are also
presented.",
committee = "Yanasse, Horacio Hideki (presidente) and Lorena, Luiz Antonio
Nogueira (orientador) and Senne, Edson Luiz Franca and Carvalho,
Solon Ven{\^a}ncio de and Armentano, Vinicius Amaral and Costa,
Alysson Machado",
copyholder = "SID/SCD",
englishtitle = "A hybrid metaheuristic with clustering search applied to
combinatorial optmization problems",
language = "pt",
pages = "197",
ibi = "8JMKD3MGP8W/34NDEC8",
url = "http://urlib.net/ibi/8JMKD3MGP8W/34NDEC8",
urlaccessdate = "2024, May 04"
}